/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    pair<ListNode*,ListNode*> reverseList(ListNode* head,ListNode* tail)
    {
        ListNode* pre=tail->next,*cur=head;
        while(pre!=tail)
        {
            ListNode* t=cur->next;
            cur->next=pre;
            pre=cur;
            cur=t;
        }
        return make_pair(tail,head);
    }
    ListNode* reverseKGroup(ListNode* head, int k) {
        ListNode* head_pre=new ListNode(0);
        head_pre->next=head;
        ListNode* pre=head_pre;

        while(head!=nullptr)
        {
            ListNode* tail=pre;
            for(int i=0;i<k;i++)
            {
                tail=tail->next;
                if(tail==nullptr)
                {
                    return head_pre->next;
                }
            }

            ListNode* tail_next=tail->next;
            auto t=reverseList(head,tail);
            head=t.first;
            tail=t.second;
            pre->next=head;
            pre=tail;
            head=tail->next;
        }
        return head_pre->next;
    }
};
